package MyDS.HashBucket;

import java.util.NoSuchElementException;

/**
 * 基于开散列方案下的哈希表实现（哈希桶）
 * @author ylc
 * @date 2022/03/27
 **/
public class HashBucket {
    private class Node{
        int key;
        int value;
        Node next;

        public Node(int key, int value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    //哈希表的实际长度
    private int size;
    //哈希表的默认长度
    private static final int DEFAULT_CAPACITY = 16;
    //默认负载因子
    private static final double LOAD_FACTOR = 0.75;
    //取模数
    private int M;
    //存储数据的数组
    private Node[] data;

    public HashBucket(){
        this(DEFAULT_CAPACITY);
    }
    public HashBucket(int initCap) {
        this.data = new Node[initCap];
        this.M = initCap;
    }

    //哈希函数
    public int hash(int key){
        return Math.abs(key) % M;
    }

    //在哈希表中添加键值对key-value
    public int add(int key, int value){
        //1.对key进行哈希运算得到哈希值索引
        int index = hash(key);
        //2.遍历这个索引对应的链表，查看当前key值是否存在
        for(Node cur = data[index]; cur != null; cur = cur.next){
            if(cur.key == key){
                //此时key存在，更新value值
                int oldVal = cur.value;
                cur.value = value;
                return oldVal;
            }
        }
        //3.不存在则新建头结点插入哈希表中
        Node node = new Node(key,value,data[index]);
        data[index] = node;
        size++;
        //4.添加一个新元素后，查看是否需要扩容
        if(data.length * LOAD_FACTOR <= size){
            resize();
        }
        return value;
    }
    //扩容
    private void resize() {
        //新数组长度增加一倍
        Node[] newData = new Node[data.length << 1];
        //将原结点的key对应到新数组
        //M值更新为新数组长度
        this.M = newData.length;
        for(int i = 0; i < data.length; i++){
            if(data[i] != null){
                Node cur = data[i];
                while(cur != null){
                    Node tnext = cur.next;
                    int newIndex = hash(cur.key);

                    cur.next = newData[newIndex];
                    newData[newIndex] = cur;

                    cur = tnext;
                }
            }else{
                continue;
            }
        }
        data = newData;
    }

    /**
     * 删除哈希表中key对应的结点
     * @param key
     * @return
     */
    public int remove(int key){
        int index = hash(key);
        // 判断头节点是否是待删除的节点
        Node head = data[index];
        if (head.key == key) {
            int val = head.value;
            data[index] = head.next;
            head.next = head = null;
            size --;
            return val;
        }
        // 当前链表的头节点不是待删除的节点
        Node prev = head;
        while (prev.next != null) {
            if (prev.next.key == key) {
                // perv恰好是待删除节点的前驱
                Node cur = prev.next;
                int val = cur.value;
                prev.next = cur.next;
                cur.next = cur = null;
                size --;
                return val;
            }
            prev = prev.next;
        }
        throw new NoSuchElementException("no such key!remove error!");
    }

    public boolean containsKey(int key) {
        int index = hash(key);
        // 遍历index位置对应的链表，查看是否有节点的key与查询的key相等
        for (Node x = data[index];x != null;x = x.next) {
            if (x.key == key) {
                return true;
            }
        }
        return false;
    }
    public boolean containsValue(int value) {
        // 遍历整个哈希表
        for (int i = 0; i < size; i++) {
            for (Node x = data[i];x != null;x = x.next) {
                if (x.value == value) {
                    return true;
                }
            }
        }
        return false;
    }
}
